#include <iostream>
#include <cstdlib>
#include <cstdbool>
#include "DoubleLinkList.h"
#include "LinkTree.h"

// 创建树节点
TreeNode* CreateTreeNode(TreeElementType element) 
{
    TreeNode *newNode = new TreeNode(element);
    if (newNode == NULL) {
        std::cerr << "create tree error!\n";
        return nullptr;
    }
    return newNode;
}

void TreeNode::ConnectBranch(TreeNode *parent, TreeNode *child)
{
    //判断节点是否为空
    if(parent == NULL || child == NULL)
        return;
    child->parent = parent;
    childs.InsertDLlistTail(child);
}

//回调函数
bool IsNodeEqual(void *ptr1,void *ptr2)
{
    //链表里的节点
    TreeNode *node1 = (TreeNode*)ptr1;
    //要删除的节点
    TreeNode *node2 = (TreeNode*)ptr2;

    return node1 == node2;
}

void TreeNode::DisconnectBranch(TreeNode *parent, TreeNode *child)
{
    //判断节点是否为空
    if(parent == NULL || child == NULL)
        return;

    //判断child是否为parent的孩子
    if(child->parent != parent)
    {
        printf("两个节点不是父子关系!\n");
        return;
    }

    child->parent = NULL;
    childs.RemoveByElement(child,IsNodeEqual,NULL);
}

void TreeNode::TravelTreeNode(TreeNode *node, int deepth, void (*PrintPtr)(void *))
{
    if(node == NULL || PrintPtr == NULL)
        return;

    if(node->parent != NULL)
    {
        //先打印自己
        for(int i = 0; i < deepth; i++)
            printf("    ");
        if(deepth >= 1)
            printf("|__");
        PrintPtr(node->data);
    }
       

    //打印所有的孩子
    DoubleLinkNode* TravelPoint = node->childs.head;
    while(TravelPoint->next != NULL)
    {
        TravelTreeNode((TreeNode*)TravelPoint->next->data,deepth + 1,PrintPtr);
        TravelPoint = TravelPoint->next;
    }
}

TreeNode *TreeNode::FindChildNode(TreeNode *parent, void *value, bool (*funcPtr)(void *, void *))
{
    DoubleLinkNode* TravelPoint = parent->childs.head;
    while(TravelPoint->next != NULL)
    {
        TreeNode *child = (TreeNode*)TravelPoint->next->data;
        if(funcPtr(child->data,value) == true)
        {
            return child;
        }
        TravelPoint = TravelPoint->next;
    }
    return NULL;
}

// 初始化一个树
LinkTree::LinkTree()
{
    root = CreateTreeNode(NULL);
}

void FreeTreeNode(void *n)
{
    TreeNode *freeNode = (TreeNode*)n;
    if(freeNode == NULL)
        return;
    //先递归释放子节点们,最后再释放自己
    freeNode->childs.ClearDList(FreeTreeNode);
    free(freeNode);
}
// 释放整个树
LinkTree::~LinkTree() 
{
    FreeTreeNode(root);
}




TreeNode *FindTreeNode(TreeNode *node,void* value,bool (*funcPtr)(void *, void *))
{
    //终止条件
    if(node == NULL || funcPtr == NULL)
    return NULL;

    //符合条件(排除根节点)
    if(node->parent != NULL && funcPtr(node->data,value) == true)
    {
        return node;
    }

    //不符合条件
    TreeNode *tragetNode = NULL;
    DLNode* TravelPoint = node->childs.head;
    while(TravelPoint->next != NULL)
    {
        tragetNode = FindTreeNode((TreeNode*)TravelPoint->next->data,value,funcPtr);
        //在孩子节点找到
        if(tragetNode != NULL)
        {
        return tragetNode;
        }
        TravelPoint = TravelPoint->next;
    }
    return tragetNode;
}


TreeNode *LinkTree::FindLinkTreeNode(void *value, bool (*funcPtr)(void *, void *))
{
    return FindTreeNode(root,value,funcPtr);
}

void FindAllLF(TreeNode *node,DoubleLinkList *list)
{
    //终止条件
    if(node == NULL)
        return;
    
    //node本身是叶子
    if(node->childs.len == 0)
    {
        list->InsertDLlistTail(node);
    }

    DoubleLinkNode* TravelPoint = node->childs.head;
    while(TravelPoint->next != NULL)
    {
        FindAllLF((TreeNode *)TravelPoint->next->data,list);
        TravelPoint = TravelPoint->next;
    }
}


DoubleLinkList LinkTree::FindAllLeafBranches()
{
    DoubleLinkList list;
    FindAllLF(root,&list);
    return list;
}
